﻿using Microsoft.VisualStudio.Diagrams.View;
using Microsoft.VisualStudio.GraphModel;
using Microsoft.VisualStudio.Progression;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using System.Windows.Media;
using Timtopia.PowerGraphBeamSearch;

namespace Timtopia.DGMLPosterView
{
    public class PowerGraphDecomposition
    {
        public static GraphSchema Schema;
        public static GraphCategory PowerEdgeCategory;
        public static GraphProperty Weight;
        static PowerGraphDecomposition()
        {
            Schema = new GraphSchema("PowerGraphDecomposition");
            PowerEdgeCategory = Schema.Categories.AddNewCategory("PowerEdge");
            Weight = Schema.Properties.AddNewProperty("Weight", typeof(int));
        }

        public static Graph CreateDecomposition(Graph original)
        {
            //CreateSimpleDescriptionFile(original);
            Graph decomposition = original.Copy();

            using (StreamWriter outfile = new StreamWriter(@"c:\temp\PGDLog"))
            {
                var sw = new Stopwatch();
                sw.Start();
                outfile.WriteLine("Starting Power Graph Decomposition...");
                Apply(decomposition, 0);
                outfile.WriteLine("Completed after" + sw.ElapsedMilliseconds);
            }
            return decomposition;
        }


        public static Graph CreateBeamsearchDecomposition(Graph original)
        {
            //CreateSimpleDescriptionFile(original);
            Graph decomposition = original.Copy();

            using (StreamWriter outfile = new StreamWriter(@"c:\temp\PGDLog"))
            {
                var sw = new Stopwatch();
                sw.Start();
                outfile.WriteLine("Starting Power Graph Decomposition...");
                DoBeamSearch(decomposition, 1000, 1, 1, 10);
                outfile.WriteLine("Completed after" + sw.ElapsedMilliseconds);
            }
            return decomposition;
        }

        public static void DoBeamSearch(Graph g, int edgeWeight, int crossingWeight, int moduleWeight, int beamSize = 10)
        {
            var nodeMap = new Dictionary<GraphNode, int>();
            var nodes = new List<GraphNode>();
            foreach (var v in g.Nodes/*.Where(n => !n.IsGroup && n.Label != "RenderControl")*/)
            {
                nodeMap[v] = nodes.Count;
                nodes.Add(v);
            }
            var edges = new List<Tuple<int, int>>();
            foreach (var l in g.Links)
            {
                try
                {
                    edges.Add(Tuple.Create(nodeMap[l.Source], nodeMap[l.Target]));
                }
                catch (Exception e)
                {
                }
            }
            var edgeLookup = new HashSet<Tuple<int, int>>(edges);
            Modules.CrossingWeight = crossingWeight;
            Modules.EdgeWeight = edgeWeight;
            Modules.ModuleWeight = moduleWeight;
            var m0 = new Modules(nodeMap.Count, edges.ToArray());
            var bs = new BeamSearch(m0, beamSize);
            var sw = new Stopwatch();
            sw.Start();
            Console.WriteLine("Starting Beam Search...");
            while (bs.Improve())
            {
                var best = bs.Best;
                Console.WriteLine("EdgeWeight={0}, CrossingWeight={1}, Cost={2}, Modules={3}, Edges={4}, Crossings={5}, BeamSize={6}, elapsed time={7} seconds", edgeWeight, crossingWeight, best.Cost, best.ModuleCount, best.EdgeCount, best.CrossingCount, beamSize, (double)(sw.ElapsedMilliseconds) / 1000.0);
            }
            using (var scope = new GraphTransactionScope())
            {
                var best = bs.Best;
                Console.WriteLine("final: EdgeWeight={0}, CrossingWeight={1}, Cost={2}, Modules={3}, Edges={4}, Crossings={5}", edgeWeight, crossingWeight, best.Cost, best.ModuleCount, best.EdgeCount, best.CrossingCount);

                // walk the module tree creating groups...
                int gid = 0;
                var nodeTreeMap = new Dictionary<TreeNode<int?>, GraphNode>();
                foreach (var t in best.Tree.InternalNodes)
                {
                    if (t.Parent == null) continue;
                    var m = best.GetModule(t);
                    var node = g.Nodes.GetOrCreate("group" + gid++);
                    node.IsGroup = true;
                    node.AddCategory(ModularDecomposition.ModuleLevelCategories[0]);
                    nodeTreeMap.Add(t, node);
                }
                foreach (var t in best.Tree.LeafNodes)
                {
                    var leaf = nodes[t.Leaf.Value];
                    AddChildForTree(g, nodeTreeMap, t, leaf);
                }
                foreach (var t in best.Tree.InternalNodes)
                {
                    if (t.Parent == null) continue;
                    var node = nodeTreeMap[t];
                    AddChildForTree(g, nodeTreeMap, t, node);
                }
                AddEdgesForModules(best, g, best.Tree, nodeTreeMap, nodes);
                g.Nodes.GetOrCreate("RenderControl");
                scope.Complete();
            }
        }

        private static void AddEdgesForModules(Modules ms, Graph g, TreeNode<int?> t, Dictionary<TreeNode<int?>, GraphNode> nodeTreeMap, List<GraphNode> nodes)
        {
            Module m = ms.GetModule(t);
            if (t.Children != null)
            {
                foreach (var c in t.Children)
                {
                    AddEdgesForModules(ms, g, c, nodeTreeMap, nodes);
                }
            }
            if (m != null)
            {
                var source = t.Leaf != null ? nodes[t.Leaf.Value] : nodeTreeMap[t];
                foreach (var e in m.Outgoing)
                {
                    var target = e.TreeNode.Leaf != null ? nodes[e.TreeNode.Leaf.Value] : nodeTreeMap[e.TreeNode]; ;
                    var l = g.Links.GetOrCreate(source, target);
                    l.AddCategory(PowerEdgeCategory);
                }
            }
        }

        private static void AddChildForTree(Graph g, Dictionary<TreeNode<int?>, GraphNode> nodeTreeMap, TreeNode<int?> t, GraphNode leaf)
        {
            if (t.Parent == null || t.Parent.Parent == null) return;
            var parent = nodeTreeMap[t.Parent];
            var clink = g.Links.GetOrCreate(parent, leaf);
            clink.AddCategory(GraphCommonSchema.Contains);
        }

        enum FileReadMode
        {
            Modules,
            Edges,
            None
        }

        public static void CreateSimpleDescriptionFile(Graph graph)
        {
            int n = graph.Nodes.Count;
            var matrix = new bool[n, n];
            var nodeArray = graph.Nodes.ToArray();
            var nodeLookup = new Dictionary<GraphNode, int>();

            for (int i = 0; i < n; ++i)
            {
                var v = nodeArray[i];
                nodeLookup[v] = i;
            }

            for (int i = 0; i < n; ++i)
            {
                foreach (var l in nodeArray[i].OutgoingLinks)
                {
                    var v = l.Target;
                    int j = nodeLookup[v];
                    matrix[i, j] = true;
                }
            }

            using (StreamWriter outfile = new StreamWriter(@"c:\temp\description.dzn"))
            {
                outfile.WriteLine("nv = " + n + ";");
                int ctr = 1;
                foreach (var v in graph.Nodes)
                {
                    if (v.Id.ToString() == "RenderControl") continue;
                    outfile.WriteLine("% " + (ctr++) + ": id=" + v.Id.ToString());
                }
                outfile.Write("edge = [|");
                for (int i = 0; i < n; ++i)
                {
                    for (int j = 0; j < n; ++j)
                    {
                        outfile.Write(matrix[i, j].ToString().ToLower() + ",");
                    }
                    outfile.Write("|");
                }
                outfile.WriteLine("];");
            }
        }

        public static Graph LoadSimpleDescription(string filename, bool originalEdges = false)
        {
            string line;

            // Read the file and display it line by line.
            System.IO.StreamReader file =
               new System.IO.StreamReader(filename);
            
            Regex moduleExpr = new Regex(@"^(b')?(\d+):\s\[([^\]]*)\]");
            Regex edgeExpr = new Regex(@"^(b')?\((\d+),(\d+)\)");

            FileReadMode mode = FileReadMode.None;

            var leaves = new HashSet<string>();
            var modules = new Dictionary<string, HashSet<string>>();
            var powerEdges = new List<Tuple<string, string>>();

            while ((line = file.ReadLine()) != null)
            {
                if (line.Contains("#modules="))
                {
                    mode = FileReadMode.Modules;
                    modules.Clear();
                    powerEdges.Clear();
                } 
                else if (!originalEdges && line.Contains("#edges=")
                    || originalEdges && line.Contains("#original edges="))
                {
                    mode = FileReadMode.Edges;
                }
                else if (mode == FileReadMode.Modules && moduleExpr.IsMatch(line) && !originalEdges)
                {
                    var match = moduleExpr.Match(line);
                    string id = match.Groups[2].Value;
                    string membersString = match.Groups[3].Value;
                    if (membersString.Length != 0)
                    {
                        var members = (from m in membersString.Split(',') select m.Trim()).ToList();
                        if (members.Count == 1 && members.First() == id)
                        {
                            leaves.Add(id);
                        }
                        else
                        {
                            modules[id] = new HashSet<string>(members);
                        }
                    }
                }
                else if (mode == FileReadMode.Edges && edgeExpr.IsMatch(line))
                {
                    var match = edgeExpr.Match(line);
                    var uid = match.Groups[2].Value;
                    var vid = match.Groups[3].Value;
                    powerEdges.Add(Tuple.Create(uid, vid));
                }
                else
                {
                    mode = FileReadMode.None;
                }
            }
            file.Close();

            Graph graph = new Graph();
            foreach (var id in leaves)
            {
                var node = graph.Nodes.GetOrCreate(id);
            }
            var sortedModules = from p in modules
                                let memberCount = p.Value.Count
                                where memberCount > 0
                                orderby memberCount
                                select p;
            foreach (var p in sortedModules)
            {
                string id = p.Key;
                var members = p.Value;
                if (members.Count == 0 || members.Count == leaves.Count)
                {
                    continue;
                }

                var node = graph.Nodes.GetOrCreate(id);
                foreach (var vid in members)
                {
                    if (vid == id) continue;
                    if (!node.IsGroup)
                    {
                        node.IsGroup = true;
                        node.AddCategory(ModularDecomposition.ModuleLevelCategories[0]);
                    }
                    var child = graph.Nodes.GetOrCreate(vid);
                    bool alreadyDescendant = false;
                    while (child.HasParentGroups)
                    {
                        if (child.HasParentGroup(graph.FindGroup(node))) {
                            alreadyDescendant = true;
                            break;
                        }
                        child = child.ParentGroups.First().AsNode();
                    }
                    if (alreadyDescendant) continue;
                    var l = graph.Links.GetOrCreate(node, child);
                    l.AddCategory(GraphCommonSchema.Contains);
                }
            }
            foreach (var e in powerEdges)
            {
                var uid = e.Item1;
                var vid = e.Item2;
                var l = graph.Links.GetOrCreate(uid, vid);
                if (!originalEdges)
                {
                    l.AddCategory(PowerEdgeCategory);
                }
                int weight = ChildCount(l.Source) * ChildCount(l.Target);
                l.SetValue(Weight, weight);
            }
            graph.Nodes.GetOrCreate("RenderControl");
            return graph;
        }

        private static int ChildCount(GraphNode node) 
        {
            if (!node.IsGroup)
            {
                return 1;
            }
            Graph graph = node.Owner;
            GraphGroup group = graph.FindGroup(node);
            int childCount = group.ChildNodes.Count;
            foreach (var v in group.ChildGroups.AsNodes())
            {
                childCount += ChildCount(v);
            }
            return childCount;
        }

        public static void Apply(Graph graph, double crossEdgePenalty = 0.5)
        {
            var V = graph.Nodes.ToArray();
            Dictionary<GraphNode, Neighbours<GraphNode>> neighbours = GetNeighbours(V);

            // we walk the similarity weight pairs in descending order, creating a greedy recursive matching
            // over the most similar
            var sorted = from w in ComputeNodeSimilarities(V, neighbours)
                         orderby w.Item1 descending
                         select Tuple.Create(w.Item2, w.Item3);
             
            // construct tree over graph nodes by matching pairs of 
            // graph nodes in weight order, heaviest first.
            var tree = PairCluster(V, sorted);

            using (var scope = new GraphTransactionScope())
            {
                // construct candidate sets by walking the tree depth first.  As we walk back
                // up the trees, we construct a candidate set for each internal node i of the tree.
                // This candidate set contains a list all leaf nodes beneath i in the tree.
                int groupCount = 0;
                var candidates = from i in tree.InternalNodes
                                 where i != tree
                                 let c = new CandidateSet(i.Leaves, neighbours, crossEdgePenalty)
                                 where c.CostDelta > 0
                                 select c;

                // repeatedly search for the best candidate and create a group for that candidate until no more edge reduction is possible.
                // SUBTLE CODE: relies on candidates being lazily instantiated at each reference!!
                CandidateSet best;
                while ((best = candidates.MaximumBy(i => i.CostDelta)) != null)
                    best.Create(graph, neighbours, "Group" + groupCount++);

                graph.Nodes.GetOrCreate("RenderControl");

                // remove original links
                graph.Links.Remove(graph.Links.Where(l => !l.HasCategory(GraphCommonSchema.Contains)));

                int powerEdges = 0;
                foreach (var pair in neighbours)
                {
                    var v = pair.Key;
                    var N = pair.Value;
                    foreach (var u in N.Incoming)
                    {
                        var l = graph.Links.GetOrCreate(u, v);
                        if (l != null)
                        {
                            l.AddCategory(PowerEdgeCategory);
                            powerEdges++;
                        }
                    }
                }

                scope.Complete();
            }
        }

        /// <summary>
        /// get pairs of nodes with non-zero similarity
        /// </summary>
        /// <param name="graph"></param>
        /// <returns>a triple with the similarity weight and the two nodes</returns>
        public static IEnumerable<Tuple<double, GraphNode, GraphNode>> ComputeNodeSimilarities(IList<GraphNode> V, Dictionary<GraphNode, Neighbours<GraphNode>> neighbours)
        {
            // for each pair of nodes with non-zero similarity, store the pair and its similarity weight
            var similarities = new List<Tuple<double, GraphNode, GraphNode>>();
            for (int i = 0; i < V.Count - 1; ++i)
            {
                var u = V[i];
                var nu = neighbours[u];
                var niuc = nu.Incoming.Union(new[] { u });
                var nouc = nu.Outgoing.Union(new[] { u });
                for (int j = i + 1; j < V.Count; ++j)
                {
                    var v = V[j];
                    var nv = neighbours[v];
                    var numerator = (nu.Incoming.Intersect(nv.Incoming)).Union(nu.Outgoing.Intersect(nv.Outgoing));
                    var denominator = nu.Incoming.Union(nv.Incoming).Union(nu.Outgoing.Union(nv.Outgoing));
                    double similarity = (double)numerator.Count() / (double)denominator.Count();

                    // the following will produce a better score for complete cliques
                    var nivc = nv.Incoming.Union(new[] { v });
                    var novc = nv.Outgoing.Union(new[] { v });

                    var numeratorC = (niuc.Intersect(nivc)).Union(nouc.Intersect(novc));
                    var denominatorC = niuc.Union(nivc).Union(nouc.Union(novc));

                    if (numeratorC.Count() == denominatorC.Count()) 
                        similarity = 1;

                    if (similarity > 0)
                    {
                        similarities.Add(Tuple.Create(similarity, u, v));
                    }
                }
            }
            return similarities;
        }

        public class Neighbours<T>
        {
            public HashSet<T> Incoming;
            public HashSet<T> Outgoing;
        }

        /// <summary>
        ///  create a map of each node's incoming and outgoing neighbours
        /// </summary>
        /// <param name="graph"></param>
        /// <returns></returns>
        public static Dictionary<GraphNode, Neighbours<GraphNode>> GetNeighbours(IList<GraphNode> V)
        {
            var neighbours = new Dictionary<GraphNode, Neighbours<GraphNode>>();

            foreach (var v in V)
            {
                neighbours[v] = new Neighbours<GraphNode>
                {
                    Incoming = new HashSet<GraphNode>(GetSourceNeighbours(v)),
                    Outgoing = new HashSet<GraphNode>(GetTargetNeighbours(v))
                };
            }
            return neighbours;
        }

        /// <summary>
        /// Construct a hierarchy over a set of T by applying the given set of pairwise matching operations in order.
        /// To match a pair of graph nodes u,v we find the
        /// ancestor tree nodes of u and v (A(u) and A(v) respectively) 
        /// that are immediate children of the
        /// lowest common ancestor tree node of u and v, LCA(u,v).
        /// A(u) and A(v) are removed as children of LCA(u,v).  We create a new set S 
        /// containing A(u) and A(v) as children.  Then S is
        /// inserted into the hierarchy as a child of LCA(u,v).
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="nodes"></param>
        /// <param name="orderedPairs"></param>
        /// <returns></returns>
        public static TreeNode<T> PairCluster<T>(IEnumerable<T> nodes, IEnumerable<Tuple<T, T>> orderedPairs)
        {
            var treeNodeLookup = new Dictionary<T, TreeNode<T>>();
            var root = new TreeNode<T>(nodes);
            foreach (var tn in root.Children)
            {
                treeNodeLookup[tn.Leaf] = tn;
            }
            foreach (var p in orderedPairs)
            {
                root.ToString();
                var a = treeNodeLookup[p.Item1];
                var b = treeNodeLookup[p.Item2];
                TreeNode<T> aAncestor, bAncestor;
                var lca = a.LeastCommonAncestor(b, out aAncestor, out bAncestor);
                if (lca.Children.Count > 2)
                {
                    lca.RemoveChild(aAncestor);
                    lca.RemoveChild(bAncestor);
                    var newNode = new TreeNode<T>(aAncestor, bAncestor);
                    lca.AddChild(newNode);
                }
            }
            return root;
        }

        public class CandidateSet
        {
            public IEnumerable<GraphNode> Members { get; private set; }
            public HashSet<GraphNode> IncomingCommon { get; private set; }
            public HashSet<GraphNode> OutgoingCommon { get; private set; }
            public double CostDelta { get; private set; }

            // improvement to cost function that will result in creating this module

            public CandidateSet(IEnumerable<GraphNode> nodes, Dictionary<GraphNode, Neighbours<GraphNode>> neighbours, double crossEdgePenalty = 1.0, double edgePenalty = 1.0)
            {
                Members = nodes;
                int totalIncomingCount = 0;
                int totalOutgoingCount = 0;
                int N = Members.Count();
                foreach (var v in Members)
                {
                    var nv = neighbours[v];
                    var externalIncoming = nv.Incoming.Except(Members);
                    var externalOutgoing = nv.Outgoing.Except(Members);
                    if (IncomingCommon == null)
                    {
                        IncomingCommon = new HashSet<GraphNode>(externalIncoming);
                        OutgoingCommon = new HashSet<GraphNode>(externalOutgoing);
                    }
                    else
                    {
                        IncomingCommon.IntersectWith(externalIncoming);
                        OutgoingCommon.IntersectWith(externalOutgoing);
                    }
                    totalIncomingCount += externalIncoming.Count();
                    totalOutgoingCount += externalOutgoing.Count();
                }

                
                // crossEdges are those that will remain after all the common edges are removed
                int crossEdgesCount = totalIncomingCount - IncomingCommon.Count * N + totalOutgoingCount - OutgoingCommon.Count * N;

                // we can remove all but one of each set of common edges
                int removableEdgeCount = (IncomingCommon.Count + OutgoingCommon.Count) * (N - 1);

                this.CostDelta = edgePenalty * removableEdgeCount - crossEdgePenalty * crossEdgesCount;
            }

            public GraphNode Create(Graph graph, Dictionary<GraphNode, Neighbours<GraphNode>> neighbours, string id)
            {
                var group = graph.Nodes.GetOrCreate(id);
                group.IsGroup = true;
                group.AddCategory(ModularDecomposition.ModuleLevelCategories[0]);

                var parent = Members.First().ParentGroups.FirstOrDefault();
                if (parent != null)
                {
                    AddChild(graph, parent.AsNode(), group);
                }

                var incomingCrossEdges = new List<GraphLink>();
                var outgoingCrossEdges = new List<GraphLink>();
                foreach (var v in Members)
                {
                    RemoveFromParent(graph, parent, v);
                    AddChild(graph, group, v);
                    var nv = neighbours[v];

                    nv.Incoming.ExceptWith(IncomingCommon);
                    nv.Outgoing.ExceptWith(OutgoingCommon);
                }

                foreach (var v in IncomingCommon)
                {
                    var nv = neighbours[v];
                    nv.Outgoing.ExceptWith(Members);
                    nv.Outgoing.Add(group);
                }

                foreach (var v in OutgoingCommon)
                {
                    var nv = neighbours[v];
                    nv.Incoming.ExceptWith(Members);
                    nv.Incoming.Add(group);
                }

                // create "power edges"
                neighbours[group] = new Neighbours<GraphNode> { Incoming = IncomingCommon, Outgoing = OutgoingCommon };

                return group;
            }

            private static void RemoveFromParent(Graph graph, GraphGroup parent, GraphNode v)
            {
                if (parent != null)
                {
                   bool removed = graph.Links.Remove(graph.Links.Get(parent.AsNode(), v));
                    Debug.Assert(removed);
                }
            }

            private static void AddChild(Graph graph, GraphNode group, GraphNode v)
            {
                var clink = graph.Links.GetOrCreate(group, v);
                clink.AddCategory(GraphCommonSchema.Contains);
            }
        }

        private static IEnumerable<GraphNode> GetSourceNeighbours(GraphNode v)
        {
            return v.IncomingLinks.Where(l => !l.HasCategory(GraphCommonSchema.Contains)).Select(l => l.Source);
        }

        private static IEnumerable<GraphNode> GetTargetNeighbours(GraphNode v)
        {
            return v.OutgoingLinks.Where(l => !l.HasCategory(GraphCommonSchema.Contains)).Select(l => l.Target);
        }

        private static TreeNode<GraphNode> GetGroupHierarchy(Graph g)
        {
            var root = new TreeNode<GraphNode>();
            foreach (var o in g.OrphanNodes)
            {
                root.AddChild(GetGroupHierarchy(g, o));
            }
            return root;
        }

        private static TreeNode<GraphNode> GetGroupHierarchy(Graph graph, GraphNode v)
        {
            TreeNode<GraphNode> treeNode;
            var g = graph.FindGroup(v);
            if (g != null)
            {
                var children = from c in g.ChildGroups.AsNodes().Concat(g.ChildNodes)
                               select GetGroupHierarchy(graph, c);
                treeNode = new TreeNode<GraphNode>(children);
            }
            else
            {
                treeNode = new TreeNode<GraphNode>(v);
            }
            return treeNode;
        }

        public class TreeNode<T> : IEnumerable<TreeNode<T>>
        {
            public T Leaf { get; private set; }
            public LinkedList<TreeNode<T>> Children { get; private set; }

            public TreeNode<T> Parent { get; private set; }
            private LinkedListNode<TreeNode<T>> parentPos;

            public TreeNode(IEnumerable<T> children) {
                foreach (var v in children)
                {
                    AddChild(new TreeNode<T>(v));
                }
            }

            public TreeNode(IEnumerable<TreeNode<T>> children)
            {
                AddChildren(children);
            }

            public TreeNode(params TreeNode<T>[] children)
            {
                AddChildren(children);
            }

            public TreeNode(T leaf)
            {
                Leaf = leaf;
            }

            public IEnumerable<TreeNode<T>> LeafNodes
            {
                get
                {
                    return from v in AggregateNodes
                           where v.Leaf != null
                           select v;
                }
            }

            public IEnumerable<T> Leaves
            {
                get
                {
                    return from v in LeafNodes
                           select v.Leaf;
                }
            }

            public IEnumerable<TreeNode<T>> InternalNodes
            {
                get
                {
                    return AggregateNodes.Where(v => v.Children != null);
                }
            }

            public IEnumerable<TreeNode<T>> AggregateNodes
            {
                get
                {
                    var stack = new Stack<TreeNode<T>>();
                    stack.Push(this);

                    while (stack.Count > 0)
                    {
                        var r = stack.Pop();
                        yield return r;
                        if (r.Children != null)
                        {
                            foreach (var c in r.Children)
                                stack.Push(c);
                        }
                    }
                }
            }

            public void RemoveChild(TreeNode<T> child)
            {
                Children.Remove(child.parentPos);
            }

            public void AddChildren(IEnumerable<TreeNode<T>> children)
            {
                foreach (var v in children) AddChild(v);
            }

            public void AddChildren(params TreeNode<T>[] children)
            {
                AddChildren((IEnumerable<TreeNode<T>>)children);
            }

            public void AddChild(TreeNode<T> child)
            {
                child.Parent = this;
                if (Children == null)
                {
                    Children = new LinkedList<TreeNode<T>>();
                }
                child.parentPos = Children.AddFirst(child);

                
            }

            internal LinkedListNode<TreeNode<T>> ParentPos
            {
                get
                {
                    return parentPos;
                }
            }

            /// <summary>
            /// Searching the ancestors of this TreeNode and the specified TreeNode b,
            /// return the first common ancestor of both.  Also outputs the least different
            /// ancestors for this and b.
            /// </summary>
            /// <param name="b">another TreeNode</param>
            /// <param name="aAncestor">our least ancestor not shared by b</param>
            /// <param name="bAncestor">b's least ancestor not shared by this</param>
            /// <returns>least common ancestor of us and b</returns>
            public TreeNode<T> LeastCommonAncestor(TreeNode<T> b, out TreeNode<T> aAncestor, out TreeNode<T> bAncestor)
            {
                TreeNode<T> lca = null;
                aAncestor = bAncestor = null;
                foreach (var p in PathFromRoot().Zip(b.PathFromRoot(), Tuple.Create))
                {
                    if ((aAncestor = p.Item1) != (bAncestor = p.Item2)) break;
                    lca = aAncestor;
                }
                return lca;
            }

            public IEnumerable<TreeNode<T>> PathFromRoot()
            {
                return PathToRoot().Reverse();
            }

            public IEnumerable<TreeNode<T>> PathToRoot(TreeNode<T> ancestor = null)
            {
                var tn = this;
                while (tn != null && tn != ancestor)
                {
                    yield return tn;
                    tn = tn.Parent;
                }
            }

            public IEnumerator<TreeNode<T>> GetEnumerator()
            {
                return new TreeNodeEnumerator<T>(this);
            }

            System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
            {
                return GetEnumerator();
            }

            public override string ToString()
            {
                string s = "";
                if (Children != null)
                {
                    s += "(";
                    foreach (var v in Children)
                    {
                        s += v.ToString() + ",";
                    }
                    s = s.TrimEnd(',');
                    s += ")";
                }
                if (Leaf != null)
                {
                    s += Leaf.ToString();
                }
                return s;
            }
        }

        public class TreeNodeEnumerator<T> : IEnumerator<TreeNode<T>>
        {
            private Queue<TreeNode<T>> next = new Queue<TreeNode<T>>();
            private TreeNode<T> current;
            private TreeNode<T> root;

            public TreeNodeEnumerator(TreeNode<T> root)
            {
                this.root = root;
                this.next.Enqueue(root);
            }

            public TreeNode<T> Current
            {
                get { return current; }
            }

            object System.Collections.IEnumerator.Current
            {
                get { return current; }
            }

            public bool MoveNext()
            {
                bool more = false;
                if (current != null && current.ParentPos != null && current.ParentPos.Next != null)
                {
                    current = current.ParentPos.Next.Value;
                    more = true;
                }
                else if (next.Any())
                {
                    current = next.Dequeue();
                    more = true;
                }
                if (current.Children != null && current.Children.Any())
                {
                    next.Enqueue(current.Children.First());
                }
                return more;
            }

            public void Reset()
            {
                current = null;
                next.Clear();
                next.Enqueue(root);
            }

            public void Dispose()
            {
            }
        }
    }

    internal static class MaximumByExtension
    {
        /// <summary>
        /// Find the maximum element in an IEnumerable considering a value obtained by the specified functor.
        /// Returns the default(T) when applied to an empty IEnumerable (unlike aggregate which throws an invalid operation exception).
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <typeparam name="V"></typeparam>
        /// <param name="s"></param>
        /// <param name="by"></param>
        /// <returns></returns>
        public static T MaximumBy<T, V>(this IEnumerable<T> s, Func<T, V> by) where V : System.IComparable
        {
            T biggest = default(T);
            V biggestVal = default(V);
            foreach (var i in s)
                if (biggest == null || by(i).CompareTo(biggestVal) > 0)
                {
                    biggest = i;
                    biggestVal = by(i);
                }
            return biggest;
        }
    }
}
